﻿using System;
using System.Collections;

namespace TheSieveOfEratosthenes {
    class Program {
        static int[] TheSieveOfEratosthenes(int MaxNum) {
            if (MaxNum > 1) {
                int[] array = new int[MaxNum];
                int[] primeArray;
                int primeNumber = MaxNum - 1;
                for (int i = 2; i < MaxNum + 1;) {
                    for (int j = 2; i * j < MaxNum + 1; j++) {
                        if (array[i * j - 1] == 0) {
                            array[i * j - 1] = 1;
                            primeNumber--;
                        }
                    }
                    do {
                        i++;
                    } while (i < MaxNum + 1 && array[i - 1] != 0);
                }
                primeArray = new int[primeNumber];
                for (int num = 2, index = 0; num < MaxNum + 1; num++) {
                    if (array[num - 1] == 0)
                        primeArray[index++] = num;
                }
                return primeArray;
            }
            else {
                return null;
            }
        }
        static void Main(string[] args) {
            int maxNumber = 0;
            int[] primeArray;
            do {
                Console.WriteLine("Input(Max Number)(Integer)(>1):");
                try {
                    maxNumber = int.Parse(Console.ReadLine());
                }
                catch (Exception e) {
                    Console.WriteLine(e);
                }
            } while (maxNumber < 2);
            primeArray = TheSieveOfEratosthenes(maxNumber);
            Console.WriteLine("Prime:");
            foreach (int num in primeArray) {
                Console.WriteLine(num);
            }
        }
    }
}
